{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Broken Board Dominoes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #graph #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #图 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: domino"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #覆盖"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为<code>1 * 2</code>的多米诺骨牌，你想把这些骨牌<strong>不重叠</strong>地覆盖在<strong>完好</strong>的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>输入：<code>n, m</code>代表棋盘的大小；<code>broken</code>是一个<code>b * 2</code>的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。</p>\n",
    "\n",
    "<p>输出：一个整数，代表最多能在棋盘上放的骨牌数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, m = 3, broken = [[1, 0], [1, 1]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。（见下图）</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/09/09/domino_example_1.jpg\" style=\"height: 204px; width: 304px;\"></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, m = 3, broken = []\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>下图是其中一种可行的摆放方式\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/09/09/domino_example_2.jpg\" style=\"height: 304px; width: 304px;\"></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= n &lt;= 8</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 8</code></li>\n",
    "\t<li><code>0 &lt;= b &lt;= n * m</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [broken-board-dominoes](https://leetcode.cn/problems/broken-board-dominoes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [broken-board-dominoes](https://leetcode.cn/problems/broken-board-dominoes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n3\\n[[1, 0], [1, 1]]', '3\\n3\\n[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        #相邻坐标（r,c）的和，奇偶性不同。 所以转化为二部图，求增广路径（折过来，着过去，W型路线）\n",
    "        Row, Col = n, m\n",
    "\n",
    "        match = [[None for _ in range(Col)] for _ in range(Row)]\n",
    "        for r, c in broken:\n",
    "            match[r][c] = '#'           #这个点不能被匹配\n",
    "\n",
    "        def dfs(r: int, c: int, visited: set()) -> bool:        #find增广路径  模板 visit直接在参数里传递了\n",
    "            visited.add((r, c))\n",
    "            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)): #有连接的边\n",
    "                if 0<= nr < Row and 0<= nc < Col:               #有连接的边\n",
    "                    nxt = match[nr][nc]     #寻找增广路径\n",
    "\n",
    "                    if nxt in visited:      #没访问过，且不是坑（坑已经在visited里面了）\n",
    "                        continue\n",
    "                    if nxt == None or dfs(nxt[0], nxt[1], visited) == True: #如果还没配对，或者配的对可以找到增广路径\n",
    "                        match[r][c] = (nr, nc)\n",
    "                        match[nr][nc] = (r, c)\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if (r + c) % 2 == 0:            #从偶集开始，从奇数集开始也行\n",
    "                    if (match[r][c] != '#'):\n",
    "                        if dfs(r, c, {'#'}) == True:\n",
    "                            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        grid = [[1] * m for _ in range(n)]\n",
    "        for b in broken:\n",
    "            grid[b[0]][b[1]] = 0\n",
    "        st = [False] * (n * m)\n",
    "        matched = [-1] * (n * m)\n",
    "        def match() -> int:\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                for j in range(i & 1, m, 2):\n",
    "                    if not grid[i][j]: continue\n",
    "                    nonlocal st\n",
    "                    st = [False] * (n * m)\n",
    "                    if (dfs(i, j)):\n",
    "                        res += 1\n",
    "            return res\n",
    "        def dfs(x: int, y: int) -> bool:\n",
    "            st[x * m + y] = True\n",
    "            for dx, dy in zip([0, 1, 0, -1], [1, 0, -1, 0]):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m: continue\n",
    "                if not grid[nx][ny]: continue\n",
    "                t = matched[nx * m + ny]\n",
    "                if (t == -1 or (not st[t]) and dfs(t // m, t % m)):\n",
    "                    matched[nx * m + ny] = x * m + y\n",
    "                    return True\n",
    "            return False\n",
    "        return match()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Hgralgorithm:\n",
    "    def __init__(self, g: list[list[int]]):\n",
    "        self.m, self.n = len(g), len(g[0])\n",
    "        self.vis = [False] * self.n\n",
    "        self.g = g\n",
    "        self.u = [0] * self.m\n",
    "        self.v = [0] * self.n\n",
    "\n",
    "    def find(self, x: int):\n",
    "        g = self.g\n",
    "        for j in range(self.n):\n",
    "            if g[x][j] and not self.vis[j]:\n",
    "                self.vis[j] = True\n",
    "                if not self.v[j] or self.find(self.v[j]):\n",
    "                    self.u[x] = j\n",
    "                    self.v[j] = x\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "    def solve(self):\n",
    "        ans = 0\n",
    "        for i in range(self.m):\n",
    "            self.vis = [False] * self.n\n",
    "            if self.find(i):ans += 1\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        m, n = n, m\n",
    "        g = [[0] * (m * n) for _ in range(m * n)]\n",
    "\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if (r + c) % 2:\n",
    "                    if [r, c] not in broken:\n",
    "                        for nr, nc in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]:\n",
    "                            if nr < 0 or nr >= m or nc < 0 or nc >= n:\n",
    "                                continue\n",
    "                            if [nr, nc] not in broken:\n",
    "                                u, v = r * n + c, nr * n + nc\n",
    "                                g[u][v] = 1\n",
    "        S = Hgralgorithm(g)\n",
    "        return S.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        conn, res = [[None] * m for _ in range(n)], 0\n",
    "        for x, y in broken:\n",
    "            conn[x][y] = (-1, -1)\n",
    "\n",
    "\n",
    "        def resolve(i, j, vis):\n",
    "            vis.add((i, j))\n",
    "            for ni, nj in [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]:\n",
    "                if 0 <= ni < n and 0 <= nj < m and conn[ni][nj] != (-1, -1):\n",
    "                    if conn[ni][nj] in vis:\n",
    "                        continue\n",
    "                    if not conn[ni][nj] or resolve(*conn[ni][nj], vis):\n",
    "                        conn[i][j] = (ni, nj)\n",
    "                        conn[ni][nj] = (i, j)\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if conn[i][j] != (-1, -1) and (i + j) % 2 == 0:\n",
    "                    res += resolve(i, j, set())\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    " def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        nb = collections.defaultdict(list)\n",
    "        broken = set(x * m + y for x, y in broken)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i * m + j in broken: continue\n",
    "                t = (i + j) & 1\n",
    "                if i < n - 1 and (i + 1) * m + j not in broken:\n",
    "                    nb[(i + t) * m + j].append((i + 1 - t) * m + j)\n",
    "                if j < m - 1 and i * m + j + 1 not in broken:\n",
    "                    nb[i * m + j + t].append(i * m + j + 1 - t)\n",
    "        match = {}\n",
    "\n",
    "        def find(x, v):\n",
    "            for y in nb[x]:\n",
    "                if y not in v:\n",
    "                    v.add(y)\n",
    "                    if y not in match or find(match[y], v):\n",
    "                        match[y] = x\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return sum(find(x, set()) for x in nb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        m, n = n, m\n",
    "        mn = m * n\n",
    "        neighbors = [[] for _ in range(mn)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i + 1 < m:\n",
    "                    neighbors[i * n + j].append((i + 1) * n + j)\n",
    "                    neighbors[(i + 1) * n + j].append(i * n + j)\n",
    "                if j + 1 < n:\n",
    "                    neighbors[i * n + j].append(i * n + j + 1)\n",
    "                    neighbors[i * n + j + 1].append(i * n + j)\n",
    "        degs = [len(neighbors[i]) for i in range(mn)]\n",
    "        for i, j in broken:\n",
    "            ij = i * n + j\n",
    "            degs[ij] = 0\n",
    "            for k in neighbors[ij]:\n",
    "                if degs[k] > 0:\n",
    "                    degs[k] -= 1\n",
    "        ans = 0\n",
    "        while True:\n",
    "            md = 5\n",
    "            tmp = -1\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    ij = i * n + j\n",
    "                    if degs[ij] > 0 and degs[ij] < md:\n",
    "                        md = degs[ij]\n",
    "                        tmp = ij\n",
    "            if tmp == -1: return ans\n",
    "            for k in neighbors[tmp]:\n",
    "                if degs[k] > 0:\n",
    "                    ans += 1\n",
    "                    degs[tmp] = 0\n",
    "                    degs[k] = 0\n",
    "                    for l in neighbors[tmp]:\n",
    "                        if degs[l] > 0: degs[l] -= 1\n",
    "                    for l in neighbors[k]:\n",
    "                        if degs[l] > 0: degs[l] -= 1\n",
    "                    break\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        #相邻坐标（r,c）的和，奇偶性不同。 所以转化为二部图，求增广路径（折过来，着过去，W型路线）\n",
    "        Row, Col = n, m\n",
    "\n",
    "        match = [[None for _ in range(Col)] for _ in range(Row)]\n",
    "        for r, c in broken:\n",
    "            match[r][c] = '#'           #这个点不能被匹配\n",
    "\n",
    "        def dfs(r: int, c: int, visited: set()) -> bool:        #find增广路径  模板 visit直接在参数里传递了\n",
    "            visited.add((r, c))\n",
    "            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)): #有连接的边\n",
    "                if 0<= nr < Row and 0<= nc < Col:               #有连接的边\n",
    "                    nxt = match[nr][nc]     #寻找增广路径\n",
    "\n",
    "                    if nxt in visited:      #没访问过，且不是坑（坑已经在visited里面了）\n",
    "                        continue\n",
    "                    if nxt == None or dfs(nxt[0], nxt[1], visited) == True: #如果还没配对，或者配的对可以找到增广路径\n",
    "                        match[r][c] = (nr, nc)\n",
    "                        match[nr][nc] = (r, c)\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if (r + c) % 2 == 0:            #从偶集开始，从奇数集开始也行\n",
    "                    if (match[r][c] != '#'):\n",
    "                        if dfs(r, c, {'#'}) == True:\n",
    "                            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        Row, Col = n, m\n",
    "\n",
    "\n",
    "        match = [[None for _ in range(Col)] for _ in range(Row)]\n",
    "\n",
    "        for r, c in broken:\n",
    "            match[r][c] = \"#\"\n",
    "\n",
    "\n",
    "        def dfs(r, c, visited):\n",
    "\n",
    "            visited.add((r, c))\n",
    "\n",
    "            for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "\n",
    "                if 0 <= nr < Row and 0 <= nc < Col:\n",
    "\n",
    "\n",
    "                    nxt = match[nr][nc]\n",
    "\n",
    "                    if nxt in visited: continue\n",
    "\n",
    "                    if nxt == None or dfs(nxt[0], nxt[1], visited) == True:\n",
    "                        match[r][c] = (nr, nc)\n",
    "                        match[nr][nc] = (r, c)\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "\n",
    "                if (r + c) % 2 == 0:\n",
    "                    if match[r][c] != \"#\":\n",
    "                        if dfs(r,c, {\"#\"}) == True:\n",
    "                            res += 1\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        #相邻坐标（r,c）的和，奇偶性不同。 所以转化为二部图，求增广路径（折过来，着过去，W型路线）\n",
    "        Row, Col = n, m\n",
    "\n",
    "        match = [[None for _ in range(Col)] for _ in range(Row)]\n",
    "        for r, c in broken:\n",
    "            match[r][c] = '#'           #这个点不能被匹配\n",
    "\n",
    "        def dfs(r: int, c: int, visited: set()) -> bool:        #find增广路径  模板 visit直接在参数里传递了\n",
    "            visited.add((r, c))\n",
    "            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)): #有连接的边\n",
    "                if 0<= nr < Row and 0<= nc < Col:               #有连接的边\n",
    "                    nxt = match[nr][nc]     #寻找增广路径\n",
    "\n",
    "                    if nxt in visited:      #没访问过，且不是坑（坑已经在visited里面了）\n",
    "                        continue\n",
    "                    if nxt == None or dfs(nxt[0], nxt[1], visited) == True: #如果还没配对，或者配的对可以找到增广路径\n",
    "                        match[r][c] = (nr, nc)\n",
    "                        match[nr][nc] = (r, c)\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if (r + c) % 2 == 0:            #从偶集开始，从奇数集开始也行\n",
    "                    if (match[r][c] != '#'):\n",
    "                        if dfs(r, c, {'#'}) == True:\n",
    "                            res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        # 相邻坐标（r,c）的和，奇偶性不同。 所以转化为二部图，求增广路径（折过来，着过去，W型路线）\n",
    "        Row, Col = n, m\n",
    "\n",
    "        match = [[None for _ in range(Col)] for _ in range(Row)]\n",
    "        for r, c in broken:\n",
    "            match[r][c] = '#'  # 这个点不能被匹配\n",
    "\n",
    "        def dfs(r: int, c: int, visited: set) -> bool:  # find增广路径  模板 visit直接在参数里传递了\n",
    "            print(visited)\n",
    "            visited.add((r, c))\n",
    "            for nxt_r, nxt_c in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):  # 有连接的边\n",
    "                if 0 <= nxt_r < Row and 0 <= nxt_c < Col:  # 有连接的边\n",
    "                    nxt = match[nxt_r][nxt_c]  # 寻找增广路径\n",
    "\n",
    "                    if nxt in visited:  # 没访问过，且不是坑（坑已经在visited里面了）\n",
    "                        continue\n",
    "                    if nxt is None or dfs(nxt[0], nxt[1], visited) is True:  # 如果还没配对，或者配的对可以找到增广路径\n",
    "                        match[r][c] = (nxt_r, nxt_c)\n",
    "                        match[nxt_r][nxt_c] = (r, c)\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if (r + c) % 2 == 0:  # 从偶集开始，从奇数集开始也行\n",
    "                    if match[r][c] != '#':\n",
    "                        if dfs(r, c, {'#'}):\n",
    "                            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        nb = collections.defaultdict(list)\n",
    "        broken = set(x * m + y for x, y in broken)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i * m + j in broken: continue\n",
    "                t = (i + j) & 1 #判断最后一位是什么，将棋盘分为两类\n",
    "                if i < n - 1 and (i + 1) * m + j not in broken: #与自己相邻的三个块是一组，相连\n",
    "                    nb[(i + t) * m + j].append((i + 1 - t) * m + j)\n",
    "                if j < m - 1 and i * m + j + 1 not in broken:\n",
    "                    nb[i * m + j + t].append(i * m + j + 1 - t)\n",
    "        match = {}\n",
    "\n",
    "# 最大匹配\n",
    "        def find(x, v):\n",
    "            for y in nb[x]:\n",
    "                if y not in v:\n",
    "                    v.add(y)\n",
    "                    if y not in match or find(match[y], v):\n",
    "                        match[y] = x\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return sum(find(x, set()) for x in nb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        x =[]\n",
    "        y = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if (i+j)%2 == 0 and [i,j] not in broken:\n",
    "                    x.append([i,j])\n",
    "                elif (i+j)%2 == 1 and [i,j] not in broken:\n",
    "                    y.append([i,j])\n",
    "        def check(x,y):\n",
    "            if abs(x[0]-y[0])+abs(x[1]-y[1]) == 1:\n",
    "                return True \n",
    "            else:\n",
    "                return False\n",
    "        def find(y,visited,choose,xs):\n",
    "            for j,x in enumerate(xs):\n",
    "                if check(x,y) and not visited[j]:\n",
    "                    visited[j] = True\n",
    "                    if choose[j] == -1 or find(choose[j],visited,choose,xs):\n",
    "                        choose[j] = y\n",
    "                        return True \n",
    "            return False\n",
    "        choose = [-1] * len(x)\n",
    "        ans = 0\n",
    "        for i in y:\n",
    "            visited = [False] * len(x)\n",
    "            if find(i,visited,choose,x): \n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Set, Tuple\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        Row, Col = n, m\n",
    "        match = [[None for _ in range(Col)] for _ in range(Row)]\n",
    "        \n",
    "        for r, c in broken:\n",
    "            match[r][c] = '#'  \n",
    "        \n",
    "        def dfs(r: int, c: int, visited: Set[Tuple[int, int]]) -> bool:\n",
    "            visited.add((r, c))\n",
    "            for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):\n",
    "                if 0 <= nr < Row and 0 <= nc < Col:\n",
    "                    nxt = match[nr][nc]\n",
    "                    if nxt in visited:\n",
    "                        continue\n",
    "                    if nxt == None or dfs(nxt[0], nxt[1], visited):\n",
    "                        match[r][c] = (nr, nc)\n",
    "                        match[nr][nc] = (r, c)\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if (r + c) % 2 == 0 and match[r][c] != '#':\n",
    "                    if dfs(r, c, {'#'}):\n",
    "                        res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        conn, res = [[None] * m for _ in range(n)], 0\n",
    "        for x, y in broken:\n",
    "            conn[x][y] = (-1, -1)\n",
    "\n",
    "\n",
    "        def resolve(i, j, vis):\n",
    "            vis.add((i, j))\n",
    "            for ni, nj in [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]:\n",
    "                if 0 <= ni < n and 0 <= nj < m and conn[ni][nj] != (-1, -1):\n",
    "                    if conn[ni][nj] in vis:\n",
    "                        continue\n",
    "                    if not conn[ni][nj] or resolve(*conn[ni][nj], vis):\n",
    "                        conn[i][j] = (ni, nj)\n",
    "                        conn[ni][nj] = (i, j)\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if conn[i][j] != (-1, -1) and (i + j) % 2 == 0:\n",
    "                    res += resolve(i, j, set())\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\r\n",
    "        #相邻坐标（r,c）的和，奇偶性不同。 所以转化为二部图，求增广路径（折过来，着过去，W型路线）\r\n",
    "        Row, Col = n, m\r\n",
    "\r\n",
    "        match = [[None for _ in range(Col)] for _ in range(Row)]\r\n",
    "        for r, c in broken:\r\n",
    "            match[r][c] = '#'           #这个点不能被匹配\r\n",
    "\r\n",
    "        def dfs(r: int, c: int, visited: set()) -> bool:        #find增广路径  模板 visit直接在参数里传递了\r\n",
    "            visited.add((r, c))\r\n",
    "            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)): #有连接的边\r\n",
    "                if 0<= nr < Row and 0<= nc < Col:               #有连接的边\r\n",
    "                    nxt = match[nr][nc]     #寻找增广路径\r\n",
    "\r\n",
    "                    if nxt in visited:      #没访问过，且不是坑（坑已经在visited里面了）\r\n",
    "                        continue\r\n",
    "                    if nxt == None or dfs(nxt[0], nxt[1], visited) == True: #如果还没配对，或者配的对可以找到增广路径\r\n",
    "                        match[r][c] = (nr, nc)\r\n",
    "                        match[nr][nc] = (r, c)\r\n",
    "                        return True\r\n",
    "            return False\r\n",
    "\r\n",
    "        res = 0\r\n",
    "        for r in range(Row):\r\n",
    "            for c in range(Col):\r\n",
    "                if (r + c) % 2 == 0:            #从偶集开始，从奇数集开始也行\r\n",
    "                    if (match[r][c] != '#'):\r\n",
    "                        if dfs(r, c, {'#'}) == True:\r\n",
    "                            res += 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        self.adjacent = defaultdict(list)\n",
    "        self.visited = [False] * (m*n)\n",
    "        self.link = [-1] * (m*n)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if [i, j] in broken:\n",
    "                    continue\n",
    "                direction = [(-1,0),(1,0),(0,-1),(0,1)]\n",
    "                for d in direction:\n",
    "                    x, y = i + d[0], j + d[1]\n",
    "                    if 0 <= x < n and 0 <= y < m and [x,y] not in broken:\n",
    "                        self.adjacent[i*m+j].append(x*m+y)\n",
    "    \n",
    "        # print(self.adjacent)\n",
    "        for u in self.adjacent.keys():\n",
    "            if self.link[u] == -1:\n",
    "                self.visited = [False] * (m*n)\n",
    "                res += self.find(u)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def find(self, u):\n",
    "        vset = self.adjacent[u]\n",
    "        for v in vset:\n",
    "            if not self.visited[v]:\n",
    "                self.visited[v] = True\n",
    "                if self.link[v] == -1 or self.find(self.link[v]) == 1:\n",
    "                    self.link[v] = u\n",
    "                    self.link[u] = v\n",
    "                    return 1\n",
    "        return 0\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        Row, Col = n, m\n",
    "\n",
    "\n",
    "        match = [[None for _ in range(Col)] for _ in range(Row)]\n",
    "\n",
    "        for r, c in broken:\n",
    "            match[r][c] = \"#\"\n",
    "\n",
    "\n",
    "        def dfs(r, c, visited):\n",
    "\n",
    "            visited.add((r, c))\n",
    "\n",
    "            for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "\n",
    "                if 0 <= nr < Row and 0 <= nc < Col:\n",
    "\n",
    "\n",
    "                    nxt = match[nr][nc]\n",
    "\n",
    "                    if nxt in visited: continue\n",
    "\n",
    "                    if nxt == None or dfs(nxt[0], nxt[1], visited) == True:\n",
    "                        match[r][c] = (nr, nc)\n",
    "                        match[nr][nc] = (r, c)\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        res = 0\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "\n",
    "                if (r + c) % 2 == 0:\n",
    "                    if match[r][c] != \"#\":\n",
    "                        if dfs(r,c, {\"#\"}) == True:\n",
    "                            res += 1\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys, os\n",
    "from typing import List\n",
    "from collections import defaultdict, OrderedDict\n",
    "\n",
    "\n",
    "class Edge(object):\n",
    "    def __init__(self, vertex0, vertex1):\n",
    "        self.vertex0, self.vertex1 = vertex0, vertex1\n",
    "        self.__hash_val = [self.vertex0, self.vertex1] if self.vertex0 < self.vertex1 else [self.vertex1, self.vertex0]\n",
    "        self.__hash_val = '_'.join(map(str, self.__hash_val))\n",
    "\n",
    "    def __hash__(self):\n",
    "        return self.__hash_val.__hash__()\n",
    "\n",
    "    def another_vertex(self, vertex):\n",
    "        return self.vertex0 if vertex == self.vertex1 else self.vertex1\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        return self.__hash__() == other.__hash__()\n",
    "\n",
    "    def __str__(self):\n",
    "        return self.__hash_val\n",
    "\n",
    "\n",
    "class EdgeSet(object):\n",
    "    def __init__(self):\n",
    "        self.vertex_adjacent = defaultdict(set)\n",
    "\n",
    "    def has_edge(self, edge: Edge):\n",
    "        v1, v2 = edge.vertex0, edge.vertex1\n",
    "        return v2 in self.vertex_adjacent[v1] and v1 in self.vertex_adjacent[v2]\n",
    "\n",
    "    def has_vertex(self, vertex):\n",
    "        return vertex in self.vertex_adjacent\n",
    "\n",
    "    def add_edge(self, edge: Edge):\n",
    "        v1, v2 = edge.vertex0, edge.vertex1\n",
    "        self.vertex_adjacent[v1].add(v2)\n",
    "        self.vertex_adjacent[v2].add(v1)\n",
    "\n",
    "    def del_edge(self, edge: Edge):\n",
    "        if self.has_edge(edge):\n",
    "            v1, v2 = edge.vertex0, edge.vertex1\n",
    "            self.vertex_adjacent[v1].discard(v2)\n",
    "            self.vertex_adjacent[v2].discard(v1)\n",
    "\n",
    "    def get_edge(self, vertex):\n",
    "        return set(Edge(vertex, n) for n in self.vertex_adjacent[vertex])\n",
    "\n",
    "    def all_edge(self):\n",
    "        return set(Edge(v1, v2) for v1, v2s in self.vertex_adjacent.items() for v2 in v2s)\n",
    "\n",
    "    def all_vertex(self):\n",
    "        return set(self.vertex_adjacent.keys())\n",
    "\n",
    "\n",
    "def build_graph(height, width, broken):\n",
    "    def coordinate_to_vertex(row, col, width):\n",
    "        return row * width + col\n",
    "\n",
    "    def look_around(row, col, height, width):\n",
    "        neighbor = filter(lambda y: 0 <= y[0] < height and 0 <= y[1] < width,\n",
    "                          map(lambda x: (row + x[0], col + x[1]), {(-1, 0), (1, 0), (0, 1), (0, -1)}), )\n",
    "        return set(map(lambda x: coordinate_to_vertex(x[0], x[1], width), neighbor))\n",
    "\n",
    "    except_vertexes = set(map(lambda x: coordinate_to_vertex(x[0], x[1], width), broken))\n",
    "    left_vertexes, right_vertexes, vertex_adjacent = set(), set(), dict()\n",
    "    for row in range(height):\n",
    "        for col in range(width):\n",
    "            vertex = coordinate_to_vertex(row, col, width)\n",
    "            if vertex in except_vertexes:\n",
    "                continue\n",
    "            if (row + col) % 2:\n",
    "                right_vertexes.add(vertex)\n",
    "            else:\n",
    "                left_vertexes.add(vertex)\n",
    "            vertex_adjacent[vertex] = look_around(row, col, height, width).difference(except_vertexes)\n",
    "    return left_vertexes, right_vertexes, vertex_adjacent\n",
    "\n",
    "\n",
    "def dfs(current_vertex, last_vertex, augmenting_path: OrderedDict, all_edges: EdgeSet, independent_edge_set: EdgeSet):\n",
    "    '''\n",
    "    交替路径查找 非匹配边-{匹配边-非匹配边}\n",
    "    :param augmenting_path: 有序字典 key为当前顶点 value为自身的前驱顶点\n",
    "    '''\n",
    "    augmenting_path[current_vertex] = last_vertex  # 把当前顶点加入增广路径 如果路径搜索失败 再把顶点退出增广路径\n",
    "    if last_vertex is not None and not independent_edge_set.has_vertex(current_vertex):  # 路径到达终点\n",
    "        return True\n",
    "    elif last_vertex is None:  # 到达路径起点\n",
    "        to_traverse_vertex = map(lambda e: e.another_vertex(current_vertex), all_edges.get_edge(current_vertex))\n",
    "    else:  # 到达路径中间点\n",
    "        if independent_edge_set.has_edge(Edge(current_vertex, last_vertex)):  # 上个边是匹配边 本轮寻找非匹配边 且非匹配边的另一顶点不在增广路径中\n",
    "            to_traverse_vertex = filter(lambda v: v not in augmenting_path,\n",
    "                                        map(lambda e: e.another_vertex(current_vertex),\n",
    "                                            all_edges.get_edge(current_vertex).difference(\n",
    "                                                independent_edge_set.get_edge(current_vertex))))\n",
    "        else:  # 上个边是非匹配边 本轮寻找匹配边\n",
    "            to_traverse_vertex = map(lambda e: e.another_vertex(current_vertex),\n",
    "                                     independent_edge_set.get_edge(current_vertex))\n",
    "    for v in to_traverse_vertex:\n",
    "        if dfs(v, current_vertex, augmenting_path, all_edges, independent_edge_set):\n",
    "            return True\n",
    "    augmenting_path.pop(current_vertex)  # 查找失败 顶点退出增广路径\n",
    "    return False\n",
    "\n",
    "\n",
    "def find_max_independent_edge_set(all_vertexes, all_edges, independent_edge_set):\n",
    "    while True:\n",
    "        augmenting_path = OrderedDict()\n",
    "        for vertex in filter(lambda v: not independent_edge_set.has_vertex(v), all_vertexes):  # 从所有非匹配点开始搜索增广路径\n",
    "            if dfs(vertex, None, augmenting_path, all_edges, independent_edge_set):\n",
    "                break\n",
    "        if augmenting_path:\n",
    "            for idx, (prev, post) in enumerate(augmenting_path.items()):\n",
    "                if prev is None or post is None:\n",
    "                    continue\n",
    "                if idx % 2:\n",
    "                    independent_edge_set.add_edge(Edge(prev, post))\n",
    "                else:\n",
    "                    independent_edge_set.del_edge(Edge(prev, post))\n",
    "        else:\n",
    "            return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        left_vertexes, right_vertexes, vertex_adjacent = build_graph(n, m, broken)\n",
    "        all_edges, independent_edge_set = EdgeSet(), EdgeSet()\n",
    "\n",
    "        # left_vertexes, right_vertexes = {0, 1, 2, 3, }, {4, 5, 6, }\n",
    "        # vertex_adjacent = {0: {4, 5, 6, },\n",
    "        #                    1: {4, 6, },\n",
    "        #                    2: {4, 5, },\n",
    "        #                    3: {6, },\n",
    "        #                    4: {0, 1, 2, },\n",
    "        #                    5: {0, 2, },\n",
    "        #                    6: {0, 1, 3, },\n",
    "        #                    }\n",
    "        # independent_edge_set.add_edge(Edge(0, 6))\n",
    "        # independent_edge_set.add_edge(Edge(1, 4))\n",
    "\n",
    "        [all_edges.add_edge(Edge(vertex, neighbor))\n",
    "         for vertex, neighbors in vertex_adjacent.items() for neighbor in neighbors]\n",
    "        find_max_independent_edge_set(left_vertexes.union(right_vertexes), all_edges, independent_edge_set)\n",
    "        for e in independent_edge_set.all_edge():\n",
    "            print(e)\n",
    "        return len(independent_edge_set.all_vertex()) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        bk = [0] * (n + 1)\n",
    "        for r, c in broken:\n",
    "            bk[r] |= 1 << c\n",
    "        @cache\n",
    "        def dp(curr, curbk):\n",
    "            if curr == n:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            def dfs(curc, addbk, cur):\n",
    "                nonlocal ans\n",
    "                if curc == m:\n",
    "                    ans = max(ans,cur+dp(curr+1,addbk|bk[curr + 1]))\n",
    "                    return\n",
    "                if curc <= m - 2 and ((1<<curc)|(1<<(curc+1))) & curbk == 0:\n",
    "                    dfs(curc + 2, addbk, cur + 1)\n",
    "                if curr < n - 1 and (1<<curc) & curbk == 0 and (1<<curc)&bk[curr + 1] == 0:\n",
    "                    dfs(curc + 1, addbk | (1 << curc), cur + 1)\n",
    "                dfs(curc + 1, addbk, cur)\n",
    "            dfs(0, 0, 0)\n",
    "            return ans\n",
    "        return dp(0, bk[0])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "\n",
    "        bk = [0]*(n+1)\n",
    "        for r,c in broken: # 先预处理初始就坏了的格子\n",
    "            bk[r]|=1<<c\n",
    "        \n",
    "        @cache\n",
    "        def dp(curr,curbk): # 处理行一定要加记忆化（其他语言用二维数组手动记忆化），这样保证每个状态只爆搜一次！\n",
    "            if curr==n: return 0 #边界条件\n",
    "            ans = 0\n",
    "\n",
    "            def dfs(curc,addbk,cur): #curc为当前列，addbk表示竖放骨牌给下一行额外附带的损坏掩码，cur为当前行放的骨牌数（包括横放和竖放）\n",
    "                nonlocal ans\n",
    "                if curc==m: #所有列已处理完就进入下一行\n",
    "                    ans=max(ans,cur+dp(curr+1,addbk|bk[curr+1])) \n",
    "                    return\n",
    "                if curc<=m-2 and ((1<<curc)|(1<<(curc+1)))&curbk==0: #横放一块骨牌，不影响下一行\n",
    "                    dfs(curc+2,addbk,cur+1)\n",
    "                if curr<n-1 and (1<<curc)&curbk==0 and (1<<curc)&bk[curr+1]==0: #竖放一块骨牌，会影响下一行\n",
    "                    dfs(curc+1,addbk|(1<<curc),cur+1)\n",
    "                dfs(curc+1,addbk,cur) #放弃（curr，curc）这个格子\n",
    "                \n",
    "            dfs(0,0,0)\n",
    "            return ans\n",
    "        \n",
    "        return dp(0,bk[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        grid = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        for x, y in broken: grid[x][y] = 1\n",
    "        @cache\n",
    "        def getNum(idx, constraints):\n",
    "            if idx == n-1:\n",
    "                cnt = 0\n",
    "                ans = 0\n",
    "                for x in constraints:\n",
    "                    if x == 1: cnt = 0\n",
    "                    if x == 0:\n",
    "                        cnt += 1\n",
    "                        if cnt == 2:\n",
    "                            ans += 1\n",
    "                            cnt = 0\n",
    "                return ans\n",
    "            ans = 0\n",
    "            new_constraints = grid[idx+1]\n",
    "            old_constraints = list(constraints)\n",
    "            possible_pos = [i for i, val in enumerate(constraints) if val == 0]\n",
    "            vertical = []\n",
    "            for item in possible_pos:\n",
    "                if new_constraints[item] == 0: vertical.append(item)\n",
    "            for i in range(2**len(vertical)):\n",
    "                current_ans = 0\n",
    "                tmp = []\n",
    "                pos = 0\n",
    "                while i:\n",
    "                    if i % 2: tmp.append(vertical[pos])\n",
    "                    pos += 1\n",
    "                    i //= 2\n",
    "                for item in tmp:\n",
    "                    old_constraints[item] = 1\n",
    "                    new_constraints[item] = 1\n",
    "                cnt = 0\n",
    "                for x in old_constraints:\n",
    "                    if x == 1: cnt = 0\n",
    "                    if x == 0:\n",
    "                        cnt += 1\n",
    "                        if cnt == 2:\n",
    "                            current_ans += 1\n",
    "                            cnt = 0\n",
    "                current_ans += getNum(idx+1, tuple(new_constraints)) + len(tmp)\n",
    "                ans = max(ans, current_ans)\n",
    "                for item in tmp:\n",
    "                    old_constraints[item] = 0\n",
    "                    new_constraints[item] = 0\n",
    "            return ans\n",
    "        return getNum(0, tuple(grid[0]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        g = [[0] * m for _ in range(n)]\n",
    "        for p in broken: g[p[0]][p[1]] = 1\n",
    "        @cache\n",
    "        def dfs(p, s):\n",
    "            if p == m * n: return 0\n",
    "            x, y = p // m, p % m\n",
    "            mx = dfs(p + 1, s[1:] + '0')\n",
    "            if y == 0:\n",
    "                if s[0] == '0' and x >= 1 and g[x][y] != 1 and g[x - 1][y] != 1: mx = max(mx, dfs(p + 1, s[1:] + '1') + 1)\n",
    "            else:\n",
    "                if s[0] == '0' and x >= 1 and g[x][y] != 1 and g[x - 1][y] != 1:mx = max(mx, dfs(p + 1, s[1:] + '1') + 1)\n",
    "                if s[-1] == '0' and g[x][y] != 1 and g[x][y - 1] != 1:mx = max(mx, dfs(p + 1, s[1:-1] + '11') + 1)\n",
    "            return mx\n",
    "        return dfs(0, '0' * m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:\n",
    "        g = [[0] * m for _ in range(n)]\n",
    "        for p in broken: g[p[0]][p[1]] = 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(p, s):\n",
    "            if p == m * n: return 0\n",
    "            mx = dfs(p + 1, s[1:] + '0')\n",
    "            x = p // m\n",
    "            y = p % m\n",
    "            if y == 0:\n",
    "                if s[0] == '0' and x >= 1 and g[x][y] != 1 and g[x - 1][y] != 1: mx = max(mx, dfs(p + 1, s[1:] + '1') + 1)\n",
    "            else:\n",
    "                if s[0] == '0' and x >= 1 and g[x][y] != 1 and g[x - 1][y] != 1:mx = max(mx, dfs(p + 1, s[1:] + '1') + 1)\n",
    "                if s[-1] == '0' and g[x][y] != 1 and g[x][y - 1] != 1:mx = max(mx, dfs(p + 1, s[1:-1] + '11') + 1)\n",
    "            return mx\n",
    "\n",
    "        return dfs(0, '0' * m)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
